package com.kevinkk.dp;

import java.util.Arrays;

/**
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 */

/**
 * 完全背包，求组合，求最小数量（而不是方法）
 * 1. dp 数组的含义
 *      dp[i] 表示 金额i 最少的硬币数量
 * 2. dp 公式
 *      dp[j] = min(dp[j], dp[j-coins[i]]+1)
 *      dp[i] 要么不拆分，要么拆分了数量 + 1，取这二者的最小值
 * 3. dp 数组的初始化
 *      由于要求最小数量，如果和其他的题目一样全部初始化为0，那么最后的值肯定都为 0，因此要初始化为 MAX_VALUE
 * 4. dp 数组的遍历方式
 *      求组合数，因此外层物品，内层背包，背包顺序遍历
 */

public class CoinChange {
    class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;

            for(int i = 0; i < coins.length; i++){
                for(int j = coins[i]; j <= amount; j++){
                    if(dp[j-coins[i]] < Integer.MAX_VALUE)
                        dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                }
            }

            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }
    }
}
